# 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。 
# 
#  岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 
# 
#  此外，你可以假设该网格的四条边均被水包围。 
# 
#  
# 
#  示例 1： 
# 
#  
# 输入：grid = [
#   ["1","1","1","1","0"],
#   ["1","1","0","1","0"],
#   ["1","1","0","0","0"],
#   ["0","0","0","0","0"]
# ]
# 输出：1
#  
# 
#  示例 2： 
# 
#  
# 输入：grid = [
#   ["1","1","0","0","0"],
#   ["1","1","0","0","0"],
#   ["0","0","1","0","0"],
#   ["0","0","0","1","1"]
# ]
# 输出：3
#  
# 
#  
# 
#  提示： 
# 
#  
#  m == grid.length 
#  n == grid[i].length 
#  1 <= m, n <= 300 
#  grid[i][j] 的值为 '0' 或 '1' 
#  
#  Related Topics 深度优先搜索 广度优先搜索 并查集 数组 矩阵 
#  👍 1365 👎 0


from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        nr = len(grid)
        nc = len(grid[0])
        result = 0
        for r in range(nr):
            for c in range(nc):
                if grid[r][c] == '1':
                    result += 1
                    q = [(r,c)]
                    while q:
                        row, col = q.pop(0)
                        for x, y in ((row-1, col), (row+1, col), (row, col-1), (row, col+1)):
                            if 0 <= x < nr and 0 <= y < nc and grid[x][y] == '1':
                                grid[x][y] = '0'
                                q.append((x, y))
        return result



# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


# 深度优先遍历
# 遍历整个图
# 如果遇到1, 深度优先, 把相连的都改为0
# 结果为深度遍历的次数
# class Solution:
#     def dfs(self, grid: List[List[str]], r, c):
#         nr = len(grid)
#         nc = len(grid[0])
#         if r < 0 or r >= nr or c < 0 or c >= nc or grid[r][c] == '0':
#             return
#         grid[r][c] = '0'
#         # 探索上下左右
#         self.dfs(grid, r - 1, c)
#         self.dfs(grid, r + 1, c)
#         self.dfs(grid, r, c - 1)
#         self.dfs(grid, r, c + 1)
#
#     def numIslands(self, grid: List[List[str]]) -> int:
#         if grid is None or len(grid) == 0:
#             return 0
#         nr = len(grid)
#         nc = len(grid[0])
#         result = 0
#         for r in range(nr):
#             for c in range(nc):
#                 if grid[r][c] == '1':
#                     result += 1
#                     self.dfs(grid, r, c)
#         return result

# 广度优先遍历, 使用队列
# 遇到1, 把相连的都标为0
# 结果为广度优先遍历的次数
#     def numIslands(self, grid: List[List[str]]) -> int:
#         if grid is None or len(grid) == 0:
#             return 0
#         nr = len(grid)
#         nc = len(grid[0])
#         result = 0
#         for r in range(nr):
#             for c in range(nc):
#                 if grid[r][c] == '1':
#                     result += 1
#                     grid[r][c] = '0'
#                     q = [(r, c)]
#                     while q:
#                         row, col = q.pop(0)
#                         for x, y in [(row-1, col), (row+1, col), (row, col-1), (row, col+1)]:
#                             if 0 <= x < nr and 0 <= y < nc and grid[x][y] == '1':
#                                 grid[x][y] = '0'
#                                 q.append((x, y))
#         return result


if __name__ == '__main__':
    s = Solution()
    g1 = [
        ["1", "1", "1", "1", "0"],
        ["1", "1", "0", "1", "0"],
        ["1", "1", "0", "0", "0"],
        ["0", "0", "0", "0", "0"]
    ]
    n1 = s.numIslands(g1)
    assert n1 == 1, n1
    g2 = [["1", "0", "1", "1", "0", "1", "1"]]
    n2 = s.numIslands(g2)
    assert n2 == 3, n2
